import java.util.*;

public class Solution {
    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public int miceAndCheese(int[] reward1, int[] reward2, int k) {
        int sz = reward1.length;
        int[] tmp = new int[sz];
        int i = 0;
        int ans = 0;
        for(i = 0; i < sz; i++){
            tmp[i] = reward1[i] - reward2[i];
            ans += reward2[i];
        }

        Arrays.sort(tmp);
        i = sz - 1;
        while(k-- > 0){
            ans += tmp[i--];
        }
        return ans;
    }

    public String removeDuplicates(String s) {
        Stack<Character> st = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            if(!st.empty() && s.charAt(i) == st.peek()){
                st.pop();
            }else{
                st.push(s.charAt(i));
            }
        }
        StringBuffer ans = new StringBuffer();
        while(!st.empty()){
            ans.append(st.pop());
        }
        return ans.reverse().toString();
    }

    //非递归实现
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null){
            return null;
        }
        Stack<TreeNode> st = new Stack<>();
        st.push(root);
        while(!st.empty()){
            TreeNode tmp = st.pop();
            list.add(tmp.val);
            if(tmp.right != null)
                st.push(tmp.right);
            if(tmp.left != null)
                st.push(tmp.left);
        }
        return list;
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        Stack<TreeNode> st = new Stack<>();
        st.push(root);
        while(!st.empty()){
            TreeNode tmp = st.pop();
            list.add(tmp.val);
            if(tmp.left != null)
                st.push(tmp.left);
            if(tmp.right != null)
                st.push(tmp.right);
        }
        Collections.reverse(list);
        return list;
    }


    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null)
            return list;
        Stack<TreeNode> st = new Stack<>();
        TreeNode cur = root;
        while(!st.empty() || cur != null){
            if(cur != null){
                st.push(cur);
                cur = cur.left;
            }else{
                TreeNode tmp = st.pop();
                list.add(tmp.val);
                cur = tmp.right;
            }
        }
        return list;
    }
}
